It is customary in the processing of data packets and particularly packets such as multicast packets which require replication, such as in a VPLS (virtual private LAN service), to store a payload of an incoming packet and to perform processing principally on a dataset (termed a ‘control entry’) while the payload of the packet is stored in memory. After replication a multiplicity of packets for dispatch are reconstituted from the derived control entries and the payload. The reconstitution usually requires the appending of different values of a particular data field (such as a header field) to the various packets and values of these fields for the various packets are termed ‘labels’.
‘Label memory’ is the name given to a particular region of memory employed for the storage of such ‘labels’. It is convenient though not always essential for the label memory to be external to the main processing ‘chip’. The smallest logical unit stored in label memory is a label. A label comprises data bits; one or more (but usually only one) of these data bits is a validity field that indicates whether the rest of the data in the label is valid.
In a label memory, labels are preferably grouped together into ‘label clusters’. Each such label cluster contains a multiplicity (N) of labels, which are very preferably stored in consecutive address locations in the label memory. Label clusters can be linked together into ‘label chains’, such that each label chain contains at least one but usually more than one label cluster.
Each label chain may be associated with a ‘pseudo wire’, i.e. a ‘logical’ wire between a minimum of two endpoints. In order to transmit a packet to the endpoints on a ‘pseudo wire’, each label in the associated label chain is read and a separate packet per valid label in the label chain is transmitted, the data in each label being used to construct the respective packet. In practice the transport from one endpoint to another includes the use of a transport label (different from the ‘pseudo-wire’ label) which is also prepended to the packet and defines the path for the next ‘hop’. At that hop the transport label is removed and replaced by another transport label which defines the path to the next hop. The pseudo-wire label is always the innermost label in the hierarchy of labels prepended. At each hop, the pseudo-wire label is also examined and if that hop is configured with it, the pseudowire is ‘terminated’ in that hop. At that stage normal layer 2 bridging lookups may be performed to determine an output port as usual.
Typically, a separate table, called herein the ‘VPLS Root Table’ contains an entry for each pseudo wire visible to the processor. Each entry in the VPLS Root Table may include three fields, namely (1) a validity bit; (2) a ‘label count’; and (3) a pointer to the start of the label chain in label memory associated with this pseudo wire. An operating program, i.e. software can provide the functions required to create label chains and also to add labels to or to remove labels from a label chain.
There are constraints on the software in implementing these add and remove functions. These constraints generally arise as consequences of the operation of the associated hardware. In particular, although (necessarily) an invalid label may appear (logically) between two valid Labels in a label chain, particularly during a process of removal, once a label has been removed there should not be a gap between labels in the label chain. Duplication of labels should not exist at any time in a label chain. All labels not being removed from a label chain should be present in the label chain. The two latter constraints mean that the labels may not themselves define duplicate packets and must not cause discard of a packet.
It is desirable to provide a technique for the efficient addition of labels to, and the removal of labels from, a label chain. In particular one requires a technique in which the constraints noted above are fulfilled, the usage of memory required to remove a label is minimal and ‘in-flight references’ to label chains are managed properly.